#@local POWERMODINT_GAP,b,bigPos,bigNeg,checkPValuationInt,data,dataHex
#@local dataInv,dataNonZero,e,f,g,i,k,m,mysource,pow,r,smlNeg,smlPos,x,y
#@local naivQM,ps,checkROOT_INT,P,a,n,p,x1,x2
gap> START_TEST("intarith.tst");
gap> 1 + 1;
2
gap> 1 - 1;
0
gap> 1 * 1;
1
gap> 1 / 1;
1
gap> RemInt(1,1);
0
gap> QuoInt(1,1);
1

#
# We need to cover four cases for (opL, opR) of each binary operation:
# (small,small), (small,gmp), (gmp,small), (gmp,gmp). In addition, due
# to the way GAP represents negative values internally, in many cases we
# also need to check positive and negative values separately, both small
# and gmp. We choose values with nice decimal representation, to make it
# easier to manually verify the results.
#
gap> smlPos := 10000; bigPos := 100000000000000000000;
10000
100000000000000000000
gap> smlNeg := -smlPos; bigNeg := -bigPos;
-10000
-100000000000000000000
gap> data := [ bigNeg-1, bigNeg, smlNeg, -1, 0, 1,smlPos, bigPos, bigPos+1 ];
[ -100000000000000000001, -100000000000000000000, -10000, -1, 0, 1, 10000, 
  100000000000000000000, 100000000000000000001 ]
gap> dataNonZero := [ bigNeg-1, bigNeg, smlNeg, -1, 1,smlPos, bigPos, bigPos+1 ];
[ -100000000000000000001, -100000000000000000000, -10000, -1, 1, 10000, 
  100000000000000000000, 100000000000000000001 ]

#
# LtInt
#
gap> List(data, x -> bigNeg < x);
[ false, false, true, true, true, true, true, true, true ]
gap> List(data, x -> smlNeg < x);
[ false, false, false, true, true, true, true, true, true ]
gap> List(data, x -> smlPos < x);
[ false, false, false, false, false, false, false, true, true ]
gap> List(data, x -> bigPos < x);
[ false, false, false, false, false, false, false, false, true ]

#
gap> List(data, x -> x < bigNeg);
[ true, false, false, false, false, false, false, false, false ]
gap> List(data, x -> x < smlNeg);
[ true, true, false, false, false, false, false, false, false ]
gap> List(data, x -> x < smlPos);
[ true, true, true, true, true, true, false, false, false ]
gap> List(data, x -> x < bigPos);
[ true, true, true, true, true, true, true, false, false ]

#
# EqInt
#
gap> List(data, x -> bigNeg = x);
[ false, true, false, false, false, false, false, false, false ]
gap> List(data, x -> smlNeg = x);
[ false, false, true, false, false, false, false, false, false ]
gap> List(data, x -> smlPos = x);
[ false, false, false, false, false, false, true, false, false ]
gap> List(data, x -> bigPos = x);
[ false, false, false, false, false, false, false, true, false ]

# Check for < on equal, but not identical large numbers
# See issue #3474
gap> x1 := 2^80;; x2 := 2^80;;
gap> x1 < x2;
false
gap> x1 = x2;
true
gap> -x1 < -x2;
false
gap> -x1 = -x2;
true

# check symmetry
gap> ForAll(data, x -> ForAll(data, y -> (x=y) = (y=x)));
true

#
# SumInt
#
gap> List(data, x -> bigNeg + x);
[ -200000000000000000001, -200000000000000000000, -100000000000000010000, 
  -100000000000000000001, -100000000000000000000, -99999999999999999999, 
  -99999999999999990000, 0, 1 ]
gap> List(data, x -> smlNeg + x);
[ -100000000000000010001, -100000000000000010000, -20000, -10001, -10000, 
  -9999, 0, 99999999999999990000, 99999999999999990001 ]
gap> List(data, x -> smlPos + x);
[ -99999999999999990001, -99999999999999990000, 0, 9999, 10000, 10001, 20000, 
  100000000000000010000, 100000000000000010001 ]
gap> List(data, x -> bigPos + x);
[ -1, 0, 99999999999999990000, 99999999999999999999, 100000000000000000000, 
  100000000000000000001, 100000000000000010000, 200000000000000000000, 
  200000000000000000001 ]

# check commutativity
gap> ForAll(data, x -> ForAll(data, y -> (x+y) = (y+x)));
true

#
# DiffInt
#
gap> List(data, x -> bigNeg - x);
[ 1, 0, -99999999999999990000, -99999999999999999999, -100000000000000000000, 
  -100000000000000000001, -100000000000000010000, -200000000000000000000, 
  -200000000000000000001 ]
gap> List(data, x -> smlNeg - x);
[ 99999999999999990001, 99999999999999990000, 0, -9999, -10000, -10001, 
  -20000, -100000000000000010000, -100000000000000010001 ]
gap> List(data, x -> smlPos - x);
[ 100000000000000010001, 100000000000000010000, 20000, 10001, 10000, 9999, 0, 
  -99999999999999990000, -99999999999999990001 ]
gap> List(data, x -> bigPos - x);
[ 200000000000000000001, 200000000000000000000, 100000000000000010000, 
  100000000000000000001, 100000000000000000000, 99999999999999999999, 
  99999999999999990000, 0, -1 ]

# check anti-commutativity
gap> ForAll(data, x -> ForAll(data, y -> (x-y) = -(y-x)));
true

#
# ProdInt
#
gap> List(data, x -> bigNeg * x);
[ 10000000000000000000100000000000000000000, 
  10000000000000000000000000000000000000000, 1000000000000000000000000, 
  100000000000000000000, 0, -100000000000000000000, 
  -1000000000000000000000000, -10000000000000000000000000000000000000000, 
  -10000000000000000000100000000000000000000 ]
gap> List(data, x -> smlNeg * x);
[ 1000000000000000000010000, 1000000000000000000000000, 100000000, 10000, 0, 
  -10000, -100000000, -1000000000000000000000000, -1000000000000000000010000 ]
gap> List(data, x -> smlPos * x);
[ -1000000000000000000010000, -1000000000000000000000000, -100000000, -10000, 
  0, 10000, 100000000, 1000000000000000000000000, 1000000000000000000010000 ]
gap> List(data, x -> bigPos * x);
[ -10000000000000000000100000000000000000000, 
  -10000000000000000000000000000000000000000, -1000000000000000000000000, 
  -100000000000000000000, 0, 100000000000000000000, 1000000000000000000000000,
  10000000000000000000000000000000000000000, 
  10000000000000000000100000000000000000000 ]

# check commutativity
gap> ForAll(data, x -> ForAll(data, y -> (x*y) = (y*x)));
true

#
# ProdIntObj
#
gap> 0 * 1.;
0.
gap> 1 * 1.;
1.
gap> 2 * 1.;
2.
gap> -1 * 1.;
-1.
gap> -2 * 1.;
-2.
gap> 2^60 * 1.;
1.15292e+18
gap> -2^60 * 1.;
-1.15292e+18

#
# PowInt
#
gap> List(data{[5..9]}, x -> 0^x);
[ 1, 0, 0, 0, 0 ]
gap> 0^-1;
Error, Integer operands: <base> must not be zero
gap> 0^-12345678901234567890;
Error, Integer operands: <base> must not be zero
gap> List(data, x -> 1^x);
[ 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
gap> List(data, x -> (-1)^x);
[ -1, 1, 1, -1, 1, -1, 1, 1, -1 ]

#
gap> List(data, x -> x^0);
[ 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
gap> ForAll(data, x -> x^1 = x);
true
gap> ForAll(data, x -> x^2 = x*x);
true
gap> ForAll(data, x -> x^3 = x*x*x);
true
gap> 2^100;
1267650600228229401496703205376

#
# PowObjInt
#
gap> [[1]] ^ smlNeg;
[ [ 1 ] ]
gap> [[1]] ^ bigNeg;
[ [ 1 ] ]
gap> [[0]] ^ smlNeg;
Error, Operations: <obj> must have an inverse
gap> [[0]] ^ bigNeg;
Error, Operations: <obj> must have an inverse

#
# ModInt
#
gap> List(dataNonZero, x -> bigNeg mod x);
[ 1, 0, 0, 0, 0, 0, 0, 1 ]
gap> List(dataNonZero, x -> smlNeg mod x);
[ 99999999999999990001, 99999999999999990000, 0, 0, 0, 0, 
  99999999999999990000, 99999999999999990001 ]
gap> List(dataNonZero, x -> smlPos mod x);
[ 10000, 10000, 0, 0, 0, 0, 10000, 10000 ]
gap> List(dataNonZero, x -> bigPos mod x);
[ 100000000000000000000, 0, 0, 0, 0, 0, 0, 100000000000000000000 ]

#
gap> List(data, x -> x mod bigNeg);
[ 99999999999999999999, 0, 99999999999999990000, 99999999999999999999, 0, 1, 
  10000, 0, 1 ]
gap> List(data, x -> x mod smlNeg);
[ 9999, 0, 0, 9999, 0, 1, 0, 0, 1 ]
gap> List(data, x -> x mod smlPos);
[ 9999, 0, 0, 9999, 0, 1, 0, 0, 1 ]
gap> List(data, x -> x mod bigPos);
[ 99999999999999999999, 0, 99999999999999990000, 99999999999999999999, 0, 1, 
  10000, 0, 1 ]

#
gap> bigNeg mod 0;
Error, Integer operations: <divisor> must be a nonzero integer (not the intege\
r 0)
gap> smlNeg mod 0;
Error, Integer operations: <divisor> must be a nonzero integer (not the intege\
r 0)
gap> smlPos mod 0;
Error, Integer operations: <divisor> must be a nonzero integer (not the intege\
r 0)
gap> bigPos mod 0;
Error, Integer operations: <divisor> must be a nonzero integer (not the intege\
r 0)

# test optimization for moduli which are a power of 2
gap> x:=2^80;
1208925819614629174706176
gap> ForAll([1..80], i -> x mod 2^i = 0);
true
gap> ForAll([1..80], i -> x mod -2^i = 0);
true
gap> ForAll([1..80], i -> (-x) mod 2^i = 0);
true
gap> ForAll([1..80], i -> (-x) mod -2^i = 0);
true

#
gap> y:=2^80-1;
1208925819614629174706175
gap> ForAll([1..80], i -> y mod 2^i = 2^i-1);
true
gap> ForAll([1..80], i -> y mod -2^i = 2^i-1);
true
gap> ForAll([1..80], i -> (-y) mod 2^i = 1);
true
gap> ForAll([1..80], i -> (-y) mod -2^i = 1);
true

# corner cases
gap> (-2^28) mod (2^28);
0
gap> (-2^60) mod (2^60);
0

# check the optimization for two large integers, one with more limbs than the other
gap> bigPos mod (bigPos*bigPos);
100000000000000000000
gap> bigNeg mod (bigPos*bigPos);
9999999999999999999900000000000000000000
gap> bigPos mod (bigPos*bigNeg);
100000000000000000000
gap> bigNeg mod (bigPos*bigNeg);
9999999999999999999900000000000000000000

#
# QuoInt
#
gap> List(dataNonZero, x -> QuoInt(bigNeg, x));
[ 0, 1, 10000000000000000, 100000000000000000000, -100000000000000000000, 
  -10000000000000000, -1, 0 ]
gap> List(dataNonZero, x -> QuoInt(smlNeg, x));
[ 0, 0, 1, 10000, -10000, -1, 0, 0 ]
gap> List(dataNonZero, x -> QuoInt(smlPos, x));
[ 0, 0, -1, -10000, 10000, 1, 0, 0 ]
gap> List(dataNonZero, x -> QuoInt(bigPos, x));
[ 0, -1, -10000000000000000, -100000000000000000000, 100000000000000000000, 
  10000000000000000, 1, 0 ]

#
gap> List(data, x -> QuoInt(x, bigNeg));
[ 1, 1, 0, 0, 0, 0, 0, -1, -1 ]
gap> List(data, x -> QuoInt(x, smlNeg));
[ 10000000000000000, 10000000000000000, 1, 0, 0, 0, -1, -10000000000000000, 
  -10000000000000000 ]
gap> List(data, x -> QuoInt(x, smlPos));
[ -10000000000000000, -10000000000000000, -1, 0, 0, 0, 1, 10000000000000000, 
  10000000000000000 ]
gap> List(data, x -> QuoInt(x, bigPos));
[ -1, -1, 0, 0, 0, 0, 0, 1, 1 ]

#
gap> QuoInt(bigNeg, 0);
Error, Integer operations: <divisor> must be a nonzero integer (not the intege\
r 0)
gap> QuoInt(smlNeg, 0);
Error, Integer operations: <divisor> must be a nonzero integer (not the intege\
r 0)
gap> QuoInt(smlPos, 0);
Error, Integer operations: <divisor> must be a nonzero integer (not the intege\
r 0)
gap> QuoInt(bigPos, 0);
Error, Integer operations: <divisor> must be a nonzero integer (not the intege\
r 0)
gap> QuoInt(fail,1);
Error, QUO_INT: <a> must be an integer (not the value 'fail')
gap> QuoInt(1,fail);
Error, QUO_INT: <b> must be an integer (not the value 'fail')

# corner cases
gap> QuoInt(-2^28, -1);
268435456
gap> QuoInt(-2^60, -1);
1152921504606846976
gap> QuoInt(-2^28, 2^28);
-1
gap> QuoInt(-2^60, 2^60);
-1

# check the optimization for two large integers, one with more limbs than the other
gap> QuoInt(bigPos, bigPos*bigPos);
0

#
# RemInt
#
gap> List(dataNonZero, x -> RemInt(bigNeg, x));
[ -100000000000000000000, 0, 0, 0, 0, 0, 0, -100000000000000000000 ]
gap> List(dataNonZero, x -> RemInt(smlNeg, x));
[ -10000, -10000, 0, 0, 0, 0, -10000, -10000 ]
gap> List(dataNonZero, x -> RemInt(smlPos, x));
[ 10000, 10000, 0, 0, 0, 0, 10000, 10000 ]
gap> List(dataNonZero, x -> RemInt(bigPos, x));
[ 100000000000000000000, 0, 0, 0, 0, 0, 0, 100000000000000000000 ]

#
gap> List(data, x -> RemInt(x, bigNeg));
[ -1, 0, -10000, -1, 0, 1, 10000, 0, 1 ]
gap> List(data, x -> RemInt(x, smlNeg));
[ -1, 0, 0, -1, 0, 1, 0, 0, 1 ]
gap> List(data, x -> RemInt(x, smlPos));
[ -1, 0, 0, -1, 0, 1, 0, 0, 1 ]
gap> List(data, x -> RemInt(x, bigPos));
[ -1, 0, -10000, -1, 0, 1, 10000, 0, 1 ]

#
gap> RemInt(bigNeg, 0);
Error, Integer operations: <divisor> must be a nonzero integer (not the intege\
r 0)
gap> RemInt(smlNeg, 0);
Error, Integer operations: <divisor> must be a nonzero integer (not the intege\
r 0)
gap> RemInt(smlPos, 0);
Error, Integer operations: <divisor> must be a nonzero integer (not the intege\
r 0)
gap> RemInt(bigPos, 0);
Error, Integer operations: <divisor> must be a nonzero integer (not the intege\
r 0)
gap> RemInt(fail,1);
Error, REM_INT: <a> must be an integer (not the value 'fail')
gap> RemInt(1,fail);
Error, REM_INT: <b> must be an integer (not the value 'fail')

# corner cases
gap> RemInt(-2^28, 2^28);
0
gap> RemInt(-2^60, 2^60);
0

# test optimization for moduli which are a power of 2
gap> x:=2^80;
1208925819614629174706176
gap> ForAll([1..80], i -> RemInt(x, 2^i) = 0);
true
gap> ForAll([1..80], i -> RemInt(x, -2^i) = 0);
true
gap> ForAll([1..80], i -> RemInt(-x, 2^i) = 0);
true
gap> ForAll([1..80], i -> RemInt(-x, -2^i) = 0);
true

#
gap> y:=2^80-1;
1208925819614629174706175
gap> ForAll([1..80], i -> RemInt(y, 2^i) = 2^i-1);
true
gap> ForAll([1..80], i -> RemInt(y, -2^i) = 2^i-1);
true
gap> ForAll([1..80], i -> RemInt(-y, 2^i) = -2^i+1);
true
gap> ForAll([1..80], i -> RemInt(-y, -2^i) = -2^i+1);
true

# check the optimization for two large integers, one with more limbs than the other
gap> RemInt(bigPos, bigPos*bigPos);
100000000000000000000
gap> RemInt(bigNeg, bigPos*bigPos);
-100000000000000000000
gap> RemInt(bigPos, bigPos*bigNeg);
100000000000000000000
gap> RemInt(bigNeg, bigPos*bigNeg);
-100000000000000000000

#
# GcdInt
#
gap> List(data, x -> GcdInt(bigNeg, x));
[ 1, 100000000000000000000, 10000, 1, 100000000000000000000, 1, 10000, 
  100000000000000000000, 1 ]
gap> List(data, x -> GcdInt(smlNeg, x));
[ 1, 10000, 10000, 1, 10000, 1, 10000, 10000, 1 ]
gap> List(data, x -> GcdInt(smlPos, x));
[ 1, 10000, 10000, 1, 10000, 1, 10000, 10000, 1 ]
gap> List(data, x -> GcdInt(bigPos, x));
[ 1, 100000000000000000000, 10000, 1, 100000000000000000000, 1, 10000, 
  100000000000000000000, 1 ]

#
gap> g:=3^10*257;; a:=g*991;; b:=g*1601;;
gap> GcdInt(2^20*a, 2^30*b) = 2^20*g;
true
gap> GcdInt(2^80*a, 2^40*b) = 2^40*g;
true
gap> GcdInt(2^80*a, 2^90*b) = 2^80*g;
true

# check symmetry
gap> ForAll(data, x -> ForAll(data, y -> GcdInt(x,y) = GcdInt(y,x)));
true

#
gap> GcdInt(fail,1);
Error, GCD_INT: <a> must be an integer (not the value 'fail')
gap> GcdInt(1,fail);
Error, GCD_INT: <b> must be an integer (not the value 'fail')

# corner cases
gap> GcdInt(0, 0);
0
gap> GcdInt(-2^60, -2^60);
1152921504606846976
gap> GcdInt(-2^28, -2^28);
268435456

#
# LcmInt
#
gap> List(data, x -> LcmInt(bigNeg, x));
[ 10000000000000000000100000000000000000000, 100000000000000000000, 
  100000000000000000000, 100000000000000000000, 0, 100000000000000000000, 
  100000000000000000000, 100000000000000000000, 
  10000000000000000000100000000000000000000 ]
gap> List(data, x -> LcmInt(smlNeg, x));
[ 1000000000000000000010000, 100000000000000000000, 10000, 10000, 0, 10000, 
  10000, 100000000000000000000, 1000000000000000000010000 ]
gap> List(data, x -> LcmInt(smlPos, x));
[ 1000000000000000000010000, 100000000000000000000, 10000, 10000, 0, 10000, 
  10000, 100000000000000000000, 1000000000000000000010000 ]
gap> List(data, x -> LcmInt(bigPos, x));
[ 10000000000000000000100000000000000000000, 100000000000000000000, 
  100000000000000000000, 100000000000000000000, 0, 100000000000000000000, 
  100000000000000000000, 100000000000000000000, 
  10000000000000000000100000000000000000000 ]

#
gap> g:=3^10*257;; a:=g*991;; b:=g*1601;;
gap> LcmInt(2^20*a, 2^30*b) = 2^30*3^10*257*991*1601;
true
gap> LcmInt(2^80*a, 2^40*b) = 2^80*3^10*257*991*1601;
true
gap> LcmInt(2^80*a, 2^90*b) = 2^90*3^10*257*991*1601;
true

# check symmetry
gap> ForAll(data, x -> ForAll(data, y -> LcmInt(x,y) = LcmInt(y,x)));
true

#
gap> LcmInt(fail,1);
Error, LcmInt: <a> must be an integer (not the value 'fail')
gap> LcmInt(1,fail);
Error, LcmInt: <b> must be an integer (not the value 'fail')

# corner cases
gap> LcmInt(0, 0);
0
gap> LcmInt(-2^60, -2^60);
1152921504606846976
gap> LcmInt(-2^28, -2^28);
268435456

#
# AInvInt
#
gap> dataInv := List(data, x -> -x);
[ 100000000000000000001, 100000000000000000000, 10000, 1, 0, -1, -10000, 
  -100000000000000000000, -100000000000000000001 ]
gap> dataInv + data;
[ 0, 0, 0, 0, 0, 0, 0, 0, 0 ]

#
# AbsInt
#
gap> List(data, AbsInt);
[ 100000000000000000001, 100000000000000000000, 10000, 1, 0, 1, 10000, 
  100000000000000000000, 100000000000000000001 ]
gap> AbsInt(-2^28) = 2^28;  # corner case on 32bit systems
true
gap> AbsInt(-2^60) = 2^60;  # corner case on 64bit systems
true
gap> AbsInt(fail);
Error, AbsInt: <op> must be a rational (not the value 'fail')
gap> ABS_INT(fail);
Error, ABS_INT: <n> must be an integer (not the value 'fail')

#
# SignInt
#
gap> List(data, SignInt);
[ -1, -1, -1, -1, 0, 1, 1, 1, 1 ]
gap> SignInt(fail);
Error, SignInt: <op> must be a rational (not the value 'fail')
gap> SIGN_INT(fail);
Error, SIGN_INT: <n> must be an integer (not the value 'fail')

#
# QuotientMod
#

# test "... q is either zero (if r is divisible by m) ... "
gap> ForAll([1..12], m -> ForAll(m*[-m..m], r -> QuotientMod(0,r,m)=0));
true

# test that 0 divides nothing other than multiples of m
gap> ForAll([1..10], m -> ForAll([1..m-1], r -> QuotientMod(r,0,m)=fail));
true

# brute force test a bunch of inputs
gap> naivQM:={r,s,m}->First([0..m-1], q -> ((q*s-r) mod m) = 0);;
gap> f := m -> SetX([-2*m..2*m], [-2*m..2*m], {r,s} -> QuotientMod(r,s,m) = naivQM(r,s,m));;
gap> Set([1..12], f);
[ [ true ] ]

# test that m = 0 is forbidden
gap> QuotientMod(5, 4, 0);
Error, Integer operations: <divisor> must be a nonzero integer (not the intege\
r 0)

# some old test cases, to show case that issue #149 is resolved
gap> QuotientMod(2, 4, 6);
2
gap> QuotientMod(4, 2, 6);
2
gap> QuotientMod(-2, 2, 6);
2
gap> QuotientMod(4, 8, 6);
2

#
# HexStringInt and IntHexString
#
gap> dataHex := List(data, HexStringInt);
[ "-56BC75E2D63100001", "-56BC75E2D63100000", "-2710", "-1", "0", "1", 
  "2710", "56BC75E2D63100000", "56BC75E2D63100001" ]
gap> HexStringInt("abc");
Error, HexStringInt: <n> must be an integer (not a list (string))
gap> List(dataHex, IntHexString) = data;
true
gap> dataHex;  # HexStringInt used to destroy its argument
[ "-56BC75E2D63100001", "-56BC75E2D63100000", "-2710", "-1", "0", "1", 
  "2710", "56BC75E2D63100000", "56BC75E2D63100001" ]
gap> IntHexString("");
0
gap> IntHexString("a");
10
gap> IntHexString("A");
10
gap> IntHexString("x");
Error, IntHexString: invalid character in hex-string
gap> IntHexString("56BC75E2D63100000x");
Error, IntHexString: invalid character in hex-string
gap> IntHexString("56BC75E2D63100000@");
Error, IntHexString: invalid character in hex-string
gap> IntHexString(0);
Error, IntHexString: <str> must be a string (not the integer 0)
gap> IntHexString("-1000000000000000");
-1152921504606846976

#
# Log2Int
#
gap> List(data, Log2Int);
[ 66, 66, 13, 0, -1, 0, 13, 66, 66 ]
gap> Log2Int("abc");
Error, Log2Int: <n> must be an integer (not a list (string))
gap> List([-5..5], Log2Int);
[ 2, 2, 1, 1, 0, -1, 0, 1, 1, 2, 2 ]
gap> ForAll([2..100], x -> Log2Int(2^x) = x and
>                         Log2Int(2^x-1) = x-1 and
>                         Log2Int(2^x+1) = x);
true
gap> ForAll([2..100], x -> Log2Int(-(2^x)) = x and
>                         Log2Int(-(2^x)-1) = x and
>                         Log2Int(-(2^x)+1) = x-1);
true

# corner cases
gap> Log2Int( 2^28 );
28
gap> Log2Int( -2^28 );
28
gap> Log2Int( 2^60 );
60
gap> Log2Int( -2^60 );
60

#
# string to integer conversion
#
gap> Int("0");
0
gap> Int("00");
0
gap> Int("01");
1
gap> Int("-01");
-1
gap> Int("100000000");
100000000
gap> Int("100000001");
100000001
gap> Int("-100000001");
-100000001
gap> Int("-100000000");
-100000000
gap> Int("123456789012345678901234567890");
123456789012345678901234567890
gap> Int("-123456789012345678901234567890");
-123456789012345678901234567890
gap> Int("");
0
gap> Int("-");
0
gap> Int("--");
fail
gap> Int("--0");
fail
gap> Int("+");
fail
gap> Int("+0");
fail
gap> Int("a");
fail
gap> Int("0 ");
fail
gap> Int(" 0");
fail
gap> Int("123456789123456789123456789123456789+1");
fail
gap> Int("A");
fail
gap> Int(['-', '1', '2', '3']);
-123
gap> Int(['1', '2', '\000', '3']);
fail

#
# integer to string conversion
#
gap> List(data, String);
[ "-100000000000000000001", "-100000000000000000000", "-10000", "-1", "0", 
  "1", "10000", "100000000000000000000", "100000000000000000001" ]
gap> String(10^2345) = Concatenation("1",ListWithIdenticalEntries(2345, '0'));
true
gap> String(-10^2345) = Concatenation("-1",ListWithIdenticalEntries(2345, '0'));
true
gap> STRING_INT(2^(64*1050));
"16432688376902041373303717503675082083474967712070846532573328644712404983810\
518956640718243568117461136366690374068651518401382303506793524181563620173242\
305610100393663331219834006258797529915534996353613850912229161562330228681697\
943119233483829381034593840718718918213141585534453862701483632397361561627587\
455119411672787580570848854607494731481630338612500020532560274582711056932696\
454609660532574559368178634626401963433432131921692120603408627119755663166987\
712330723579505258138768167133091086980695632844319654073520789696983183333175\
250923946466389309146306446769103122556794749926734836181187558988098763371439\
137708373273057414269960776907242486195700506789306223651743700088132889303562\
358982425705588606698414966314762068064581009605194054843315841363413643308325\
171766921578969070132358377766102863165999450397553297430702919179955167133284\
498682185298237104271982290198674445343323391731002512873070667384922683407494\
837397265492449039064326003408414546013252864646637300586605813623096304146257\
136697447645082313098398879674825833030522204627996746089025157500974424191650\
475289754118768580264106703856764069569519026403578108428931192987163974542653\
909927542087055266175630473078819896912854000361973064521600055862250136106097\
592270156990853386363383090944563054176482017066725476249710988088048103085863\
730771366688653632552976614411033863023361226477863811821474621257928493819227\
715405332591584626702359898615282571341474835846294984836760592661248260532277\
920840082053707335029045195364510969780001693877740342558953724777752742510369\
556587519852062421878733221638704391920618270617815127100969108334167858476232\
437177928898356361823858101208624630901604528245799217359984443246568006858556\
605672304522061977522651506281570124123104306136190773114281931004649755613708\
497314072270152762033882003155099743414284500196239724872918682815834175993469\
311836963601335045885077090628096841031294444899461111374743596482560878148328\
265555077746262175801686744559421754312874983919403121660849059809350944369370\
811119003185933029399827199753386845844838523629208005523601611085887433529615\
503554586425504670394147150852407708908263549800907522473972475960236394151558\
782250537225893609657477177907207054533010966285324612424599397605472658162205\
849307900981342203572106412933173265688903551568111978652010113287692340788975\
091937988067969121986708664358012020590173373848427935129503386430005829748751\
444480692865992591927029534590361672855377670311703417089816469474761251836160\
649186349096507437334667323690495146153306704144898041945703452678583641493324\
010367375683864021736368320155334741193162820947987011252556282752096267317066\
420306365674548015350076242153094709096484989518247909051383569775333448923030\
045486002796324512257906426015951826786064091452896105813124041045247464214018\
591105663698796567333248883468565056753977973446123509696710710692633077824878\
289325170332019180114699686351682275365226586396809729782091544781888019150161\
505281827414262287592401617513010679863234737797293951761447500297249928746504\
496184565763966048275193972289544873012897906375819266786412010562420856820075\
768504713507176205279862272472734336341235139333521830918586962574204678670819\
091991068580505120981639075715037457254162164811550995333365565539311422498831\
052446634978004372999772194055817259823569678554127733319622267771654004116796\
323380269553536207413399636830923383323834278869162752487482127398903392429771\
003618070263304170259377076466221013012045371447230957710513952817611452250448\
887438164797463387206876157593083431758099604575893070423003525579979747013759\
903398983918801974385290778194511710980006300958745085663018863693860301075855\
253400963222249889055771925742285904217495576473679860327153046904815965578939\
481932718025490349706630173474024615059557833643231977206996052533667528567261\
326892683896153450813768931474111970773631996483684392320510966566832560890720\
315397494404949006129771149736930642854336774418528198326219061863557644280571\
780723893090127756554445727343630047097829611166743706106472143202711328478936\
640512163017772500272753287215353721971115690485301723485541645060542601284958\
273932117216719561120887997639675113218560053866077312919236422681173912339516\
353096555744567785615997419077316504958758042592184080712496550804521494775983\
552326215119705685961995884534645884583917606864709580319777475411265558900646\
359639433843469198967123293785353696798225856391927457895115757247371407841105\
887074172061729969735756608125216064292780482073184030203719177913186139548809\
145554516356585597369604822226843588041575417043345994588069793212903845080266\
969314870626917840383100132036437588060165059854246456918686658387431702619864\
910329188575534734168627518504669234585862135585194654561593550170128077345988\
277258486343791358581180522974585877414531093883107624815200540297664220404376\
682942639754051532274254031883971647161950360109338910047569943809910335936267\
647457293600833726930496064410163148481930865932149496095999161418525553545606\
183852480040176911298632213880539362744339806106866019251169837251481547118122\
959152193873714226509552494891577102599272811974775083367992107789178632556923\
157910580734144258714400632276444280492556520729505656292897687927088237996624\
823606578015166175050833172105691551189773960062380595711148791711548300660160\
253432881596622259550547926482292041419032238424217472898798567306115581482307\
441729570877121301256754022310837949364824085147263063599235811064010128834436\
510343318926939493120455884844879352374925236608933851357193857375232737729994\
765110786126341550144749082134863662900498120848654401063628162518596970859133\
934027875936969243232946037646649160344904855040727611597672426333410453301016\
206851447472706082194154206746560032908963220204535556309852625631420330400629\
844030779229915296324521591474117942029743735088768087398902071401225013161764\
394376572852653826550649703040806984281432784780276082453952701246915924996820\
944038615752110672482509715137259136388313334997212109951681879887757634965234\
509236560895844677303467450230350319589579552117487075763490208552793349284057\
928629806675288241446500259852346561014004363412699254791338520146684078627909\
613833147644855504459741750227441644902673652481264274984775997088905331369203\
586188946742217157686020613364429182979677200693403240253797532670250584695508\
363465220323061879893563995514504340409325283891816914394478109608861316310916\
631299372679200310957982686141340780647215724712586392600606336305541271110274\
483597369896506533598742908486034124878870826157040165000932967536247816344035\
558477498964904388232765508804640431142616949032313140303752586869132272643017\
252556699352718469664028713295927678704320306167161183931530891284569777677996\
804070856865369079672707123418073759821879995153423454337839997975279806841939\
168569563990129381934656567147758086823838041255376297913298350692294617950097\
307237242409152990420780492910196277831524996458086005162314305765082863690308\
765062323914393600626115019649603948112556185906300365745601687669221991293930\
364993435477868234408773833490771459713202255101619855007788509104661282715800\
545359888618711039859720022637780449726902939095658192277270395749187728352183\
396523455769571346043469152462400464189111696677878208644666838224067150178435\
237323802664878496431379527980004253582893966980985882567806647094939406686636\
826258682387057577279571565987148868878457130204976524820241208916950393088832\
349059996664933672318043365134165910475149760166985061385076677103823765269090\
741813785698044454046715730447311255215387492488813258207864129961543018654931\
548332426222472845653784537540330900352256376323847735454254359255031552951715\
681441999289975154808767139787671392028761127897862044545246432053208797130095\
907799805999649090145069605631502953731285661377667216954591931189962167502269\
525488519020543198038327331391336481223849896874638617975880151970521589737417\
751517888641727145770863698721906849127255094247610479561873963638766969504416\
044371159758878573690143716672670928450680720512624113023155998368698667449696\
334102652121691063993275691333193942139919405692604994391712134812284125844576\
911953892944774412751149719532710810942982942232746565694259900774124056642471\
447604325754322972586652513995310314657152105516698331940311305583669741334604\
073227645768236684841312574519473570265646247385527416336420092065428836213386\
926300040889957844593453047064856730497773498159142755543158943108136483292153\
732009528634398509325451975408412636835495932588407633977660962865464672905361\
075493887117580751223195322105718543254828245433695121249269467124011298520704\
127887084959512521544646604485945299993487372420593645414254714510021831470973\
356655010994842036057272936139211371099240264695441798493351020967024949843184\
910080784613549764198840774475349137075296559920099086431814691471014017921898\
384225865489463715346915381227805895029852244337414494596140331735248933281901\
736208905437650678553709793430972043091324630623209056891649268149415237904021\
246759230032770879795953977837615885019833590323668818501387528052852776290999\
038351138934821842471444873577871571850726911341671905813214045416754794428516\
750856234869436972057249942054703716699847232931966886508025841873729378462836\
911639696744335395419333907619144897130891642795977538910719769121906654090358\
584339620142168256126438047322229516971328805074478242801357940056986116534780\
174095875579259821690504429179257550088796129666357445415765701501479466201283\
200276398795399686481113051034190663425714303913347791017196051451032677341730\
047335087626172763705457958409461522503819132810885591485799232256515803035702\
994869466775116728722612875583007329195599496060868229984080013637130308219374\
410298470651493579476829408583714506376921560626590277157406954541419804807168\
232395301897886390861046154615600416290198638482377210391155790047895014999014\
750564266463531384203960623928797222958170726840257598331838925548857324584845\
567205151380499526224751036556534377507539897148710801490852380054229827381231\
189100956564708278973349773667934167961336279820342405717614240129236168991438\
260065664307624369547506550312512471356330361233624254518079407470075628742877\
891804385075640466469702969249231767896138663959990461513622204777418263723788\
358203861230058612600681268712963633839498918063883542227004747208194744452738\
059047416003193062424137506412101941530465356673208897234221181094950011195909\
501165948172584129903388302903654276784338337716567319814051798823566334881180\
438019074786210874988964602418298913046620645433431338826580874784769318541408\
384690719309239341655610541149706676911468957339965224715607518996659011614038\
602429908689296208745512906680510895204964461491378943808491407964789356795967\
690019377464323945572895473741734351874229718693874989287500528259076380641050\
834344055132113915369149280268306961708738697813983117399557494177019621840921\
208620040255958196374590380922620916766756732031502704169685873451759771253703\
148130698373952808057937462237020080788856963282456103855530113006494788431982\
757339104954444754665499314708550159389707535425647939882528071070469324608904\
954423325145812933531554906269351432311098080915995812869446694030739224076924\
111816939267350620782827163871678730465364429326320501024893826125648847260105\
582178009051172016905300913434923242381058866184121796645017219810939267923273\
059500781819825492182637685850050568629984902795902141201218481472488178637195\
166816420602290505985236498999230271180973669128492829464079518992163914700992\
465028218694966502409245811349512490568327897298237721297914579420159137876162\
548824305978975574373828622741916497379816296797544658996444183099449481957390\
081799166385911640472733000072362032442699445071220446296058258019448636565384\
427027842407706412622648052360239344751137293268878946543145236363183760561253\
297292040044409669945568773876489730477057898441545091734308594468217483599297\
603210966379373615717309659993000600919650227931122959315943314621973305691341\
346755217977355319679416128456701468933194023284312031029473741964280428539371\
142314203944153855280411654085252708583105203139096859025023089295872843428663\
903011450475524761264826335645273199516097699539055000006210431564941453780452\
603950053108078414189090731581547683548566701261647916912223968455464070077518\
335732280253703484803214038397373654669416248766732350348374579356245190094313\
522173757034062088837084057378960569746949224355301623712637716701378559847125\
409928230692667918476897307709647286716567582297274519994177798931308885149719\
850308364867677865569397165940515724780197850929779400392642801045133791217780\
098461792692808134034310663544499260609346193002585698754014438695728954271291\
770840491944014278559100496560639033502288605605951456024876867508741343976432\
344787714401125055610318724607778697334767277735381555068493438053689946806933\
410471613640231597434124324203468430159317810233274736801262802071502726195295\
071717469081865451659520696514957307596769152479549869123139831398784194024441\
150330941005643679533613718138074578181767453587591068642867585212062477118505\
133908821827476141043145934748278594611913143446999829520247076218607566208729\
613536084999309362983227970900500089718508616178769558173043920101188229066599\
632400553741684703679723855200588490930169837745321854565117589292288542956391\
217738016140688109192790968116936164714514051669152226836918223659124408906325\
072221954452606667569855382860974016148511232687707740422583588082859440452875\
264529108385456267485533455771560313834932991646298074460261654186069928516498\
479819289552744626033671607901851192912460686994032399811269777177267618097053\
235919331083869664941216691328693997366967283068349905107006549920485125069006\
550448727696585691139203528863922359969640304751525781518944894558932527552709\
867977428584672554934131374086961074349732383041906553772143304321594453692452\
480103659343083363487959421847642929063441165811363630027658777935309878831094\
731161201657620078856450854576598907866507823877540340379869280509127019437951\
377121357669366307665555321442940596220846987787171769821475128403337816303702\
735284278948388145653394151974606525657735820365707149825468976397804188062395\
562499208810744467337973737991087790152713843551980944567633654507615962644956\
037625898694970874093522967615606502094914204010133372061731108749695093704862\
024912619678685675729590914245534192929495157558976789713149445643679671619551\
956214022587160351709468286384178334048976365940689974863721746584189457374004\
096676950758604501012137656790415156120353056117093981261539735386043753504072\
286186147862308720894549754266809740236475594489493153817209198286631671908967\
119701093529833182452273813796897591048112410168935448810548093654237832415177\
841029847245643671202812612409632988442261843367852274492355756329607989451763\
285582978138648811867285862727681761443735498641989437533768376437034165926089\
993009827182863714412082747944137410025099366984059299018971130148752235159307\
117595891941526908583345257083317003032341070788263221258955920330966452368134\
726623011966213643354197092994459197458177575780746209262275507170860793119826\
814507666960668877362758058492400697188917977264223563265945932863664622525885\
368196603935762256938713666902843955207532257413278066694191361447822721731186\
529740712266030826752821176238895343388835195822021806411734159761303179673939\
579271435754276579571331096630027332323869582048631384979226534504759896275636\
062831584650387451285472369192238679689942598199364802775714870291279498296921\
130304436300860291611538945931918591912913847922624823249999908241298389265837\
358860231271026330666272391707006143232963567909867212127105041054224034521993\
949255226182138316489222455035459981477377806440996427166659502772157111894823\
099268637280064329524395303980192715417542309069021266549944701687258355537153\
626490634019616215162934749865426262841906882161758624919714811245811912906851\
842317665696444334824988404972730305235384562753379354825541537972258708388067\
029004850453129214940066009109105145554792438949804412500018519534687970181498\
736102713007785103819118631429355392916581189649503510578164873642787692382362\
476855653919680036439817468480545746973160334313222021021255096345319300336234\
646890905590773269715038183101520401329840692737924087169312955807272970718458\
018630551152650425308751839299675443216089598130090161387379492620294297082864\
075062080181488630988675579236948446976221942762150037444542650505553561884655\
962579829279749362862315411415971481237086595665101467843236563893049356726130\
862436953442581352212151483334478110381597144071149072915557741032846029471316\
868753887689506843226999127406799402690341678503889657136154130360954202157247\
728329011285460421716872145906210098357040604182830511151618579349464071952528\
032103766077818785427242712127469364684161477311462933191404387646117870857761\
467294937731578500323322217203369762980582848492310120103558661111080156405670\
251598363651051991566217721145551486061262711129038722634206246377161032862309\
231159193143990793051502615175037072979410191135899777644691289173185671969098\
166464198814455451795235662096940591761918604300000522668492635051558666636711\
065501292460340308719795491322362776812340215673464702088210777906827175789392\
440033334660102098366575375238031644887949254528957735036376940451148552615363\
391642464235175665552562577984829275444642743923878938691579475341887519130076\
608731703921597770086580055355598063239567295077655773948662122122675024244382\
996188682214774638078212078802443830099946591567071563784648620573611014000635\
525050175624173191599128922840707048206244022665092730405123768559338458675182\
099416656451307720455955070040885306758408727902737461036072641516781109520794\
507036853608427897270817115382463919914281932999736524909005967876617990006729\
101181131806363220028599659778348171962605675653373274975893542817861600953231\
252324152953051474706804569960344757181235044174072497590120075198338233354191\
361648160768446417693467701334934747346039043646173516003421447844305336787190\
464469545957159075638994220608388396797594503810865249016738800890758262107605\
836403279617155586957440055347218377885958299749868950516157841619379649500562\
933972813356695532993304933500534044404566417076404984911048977856371003030641\
894246070142671842147610033177876614760331955660521839194430538871760201158299\
552589648431513664621868286669011154781741928754002435841244478979800030061982\
000808437628285375706683567840838443251289388892723568762941893118852489525428\
628251855165854138742268450537715753828943881263359217794580701881422153033953\
702382376225884713342595200061015331894249850790492503589957204738992129671231\
087129376234493149614871272025255929545428613203045429549880764425905365023624\
643660529727927322436421292635085224351861927144511471701114751938634359789137\
606410097806054525755691534167732940399075291334478890472473956392771617667321\
758631652229596567485774758291985339523540833762524747359698614478695609653040\
796120671293365133765885109666948031679624569135500649560641655934818588841154\
649506135219178855519572577936270442565001652279648948804823223796267452700598\
796593185054103967277906092371176795868030052057812732338087911595397862829573\
736309938934716740828666812699761855846777479766008154011376877088294162132623\
179815414912784227117818670956194195108056539836355241038628735135087870760928\
442559294364872096891526109903897875472740768999652314155371499722161322814566\
557264364907370862762525992457349009153270938100745586736497958308782267418733\
935246203095869966256390100358242731445080378636431459452908399717935069499521\
690983388979179145884187755733084200789835331119507100627639557107627871261529\
879242349612508748825664710411040842049377536164384233624681240879881015634086\
581627733464948817122577130042937085828730931030539731358775462226186271004021\
921602051206410833294106516412412224927039055722049943821715902449488344590998\
372561851557736593496185667243743138539622865137297522714623988063679374434333\
043212644256310766508806470547630696859572759762956470857184976722693245835723\
953631635925765015465470960121525139930118355061405240095695214478686152763696\
458381012040436713717847441373878992443750202425721317922485282855600755950012\
694868859981748182733043463404121437494760145844055905688381975686244812453732\
18157000453169824579899621376"

#
# RandomIntegerMT
#
gap> mysource := RandomSource(IsMersenneTwister, 42);;
gap> Random(mysource, 1, 2^20);
732950
gap> Random(mysource, 1, 2^40);
103724225096
gap> Random(mysource, 1, 2^80);
1071135285340982180054653
gap> RandomIntegerMT(fail, 1);
Error, RandomIntegerMT: <mtstr> must be a string (not the value 'fail')
gap> RandomIntegerMT("abc", 1);
Error, RandomIntegerMT: <mtstr> must be a string with at least 2500 characters
gap> RandomIntegerMT(mysource!.state, fail);
Error, RandomIntegerMT: <nrbits> must be a non-negative small integer (not the\
 value 'fail')

#
# PrintInt
#
gap> for n in data do PrintObj(n); Print("\n"); od;
-100000000000000000001
-100000000000000000000
-10000
-1
0
1
10000
100000000000000000000
100000000000000000001
gap> Print(2^(64*1050), "\n");
164326883769020413733037175036750820834749677120708465325733286447124049838105\
189566407182435681174611363666903740686515184013823035067935241815636201732423\
056101003936633312198340062587975299155349963536138509122291615623302286816979\
431192334838293810345938407187189182131415855344538627014836323973615616275874\
551194116727875805708488546074947314816303386125000205325602745827110569326964\
546096605325745593681786346264019634334321319216921206034086271197556631669877\
123307235795052581387681671330910869806956328443196540735207896969831833331752\
509239464663893091463064467691031225567947499267348361811875589880987633714391\
377083732730574142699607769072424861957005067893062236517437000881328893035623\
589824257055886066984149663147620680645810096051940548433158413634136433083251\
717669215789690701323583777661028631659994503975532974307029191799551671332844\
986821852982371042719822901986744453433233917310025128730706673849226834074948\
373972654924490390643260034084145460132528646466373005866058136230963041462571\
366974476450823130983988796748258330305222046279967460890251575009744241916504\
752897541187685802641067038567640695695190264035781084289311929871639745426539\
099275420870552661756304730788198969128540003619730645216000558622501361060975\
922701569908533863633830909445630541764820170667254762497109880880481030858637\
307713666886536325529766144110338630233612264778638118214746212579284938192277\
154053325915846267023598986152825713414748358462949848367605926612482605322779\
208400820537073350290451953645109697800016938777403425589537247777527425103695\
565875198520624218787332216387043919206182706178151271009691083341678584762324\
371779288983563618238581012086246309016045282457992173599844432465680068585566\
056723045220619775226515062815701241231043061361907731142819310046497556137084\
973140722701527620338820031550997434142845001962397248729186828158341759934693\
118369636013350458850770906280968410312944448994611113747435964825608781483282\
655550777462621758016867445594217543128749839194031216608490598093509443693708\
111190031859330293998271997533868458448385236292080055236016110858874335296155\
035545864255046703941471508524077089082635498009075224739724759602363941515587\
822505372258936096574771779072070545330109662853246124245993976054726581622058\
493079009813422035721064129331732656889035515681119786520101132876923407889750\
919379880679691219867086643580120205901733738484279351295033864300058297487514\
444806928659925919270295345903616728553776703117034170898164694747612518361606\
491863490965074373346673236904951461533067041448980419457034526785836414933240\
103673756838640217363683201553347411931628209479870112525562827520962673170664\
203063656745480153500762421530947090964849895182479090513835697753334489230300\
454860027963245122579064260159518267860640914528961058131240410452474642140185\
911056636987965673332488834685650567539779734461235096967107106926330778248782\
893251703320191801146996863516822753652265863968097297820915447818880191501615\
052818274142622875924016175130106798632347377972939517614475002972499287465044\
961845657639660482751939722895448730128979063758192667864120105624208568200757\
685047135071762052798622724727343363412351393335218309185869625742046786708190\
919910685805051209816390757150374572541621648115509953333655655393114224988310\
524466349780043729997721940558172598235696785541277333196222677716540041167963\
233802695535362074133996368309233833238342788691627524874821273989033924297710\
036180702633041702593770764662210130120453714472309577105139528176114522504488\
874381647974633872068761575930834317580996045758930704230035255799797470137599\
033989839188019743852907781945117109800063009587450856630188636938603010758552\
534009632222498890557719257422859042174955764736798603271530469048159655789394\
819327180254903497066301734740246150595578336432319772069960525336675285672613\
268926838961534508137689314741119707736319964836843923205109665668325608907203\
153974944049490061297711497369306428543367744185281983262190618635576442805717\
807238930901277565544457273436300470978296111667437061064721432027113284789366\
405121630177725002727532872153537219711156904853017234855416450605426012849582\
739321172167195611208879976396751132185600538660773129192364226811739123395163\
530965557445677856159974190773165049587580425921840807124965508045214947759835\
523262151197056859619958845346458845839176068647095803197774754112655589006463\
596394338434691989671232937853536967982258563919274578951157572473714078411058\
870741720617299697357566081252160642927804820731840302037191779131861395488091\
455545163565855973696048222268435880415754170433459945880697932129038450802669\
693148706269178403831001320364375880601650598542464569186866583874317026198649\
103291885755347341686275185046692345858621355851946545615935501701280773459882\
772584863437913585811805229745858774145310938831076248152005402976642204043766\
829426397540515322742540318839716471619503601093389100475699438099103359362676\
474572936008337269304960644101631484819308659321494960959991614185255535456061\
838524800401769112986322138805393627443398061068660192511698372514815471181229\
591521938737142265095524948915771025992728119747750833679921077891786325569231\
579105807341442587144006322764442804925565207295056562928976879270882379966248\
236065780151661750508331721056915511897739600623805957111487917115483006601602\
534328815966222595505479264822920414190322384242174728987985673061155814823074\
417295708771213012567540223108379493648240851472630635992358110640101288344365\
103433189269394931204558848448793523749252366089338513571938573752327377299947\
651107861263415501447490821348636629004981208486544010636281625185969708591339\
340278759369692432329460376466491603449048550407276115976724263334104533010162\
068514474727060821941542067465600329089632202045355563098526256314203304006298\
440307792299152963245215914741179420297437350887680873989020714012250131617643\
943765728526538265506497030408069842814327847802760824539527012469159249968209\
440386157521106724825097151372591363883133349972121099516818798877576349652345\
092365608958446773034674502303503195895795521174870757634902085527933492840579\
286298066752882414465002598523465610140043634126992547913385201466840786279096\
138331476448555044597417502274416449026736524812642749847759970889053313692035\
861889467422171576860206133644291829796772006934032402537975326702505846955083\
634652203230618798935639955145043404093252838918169143944781096088613163109166\
312993726792003109579826861413407806472157247125863926006063363055412711102744\
835973698965065335987429084860341248788708261570401650009329675362478163440355\
584774989649043882327655088046404311426169490323131403037525868691322726430172\
525566993527184696640287132959276787043203061671611839315308912845697776779968\
040708568653690796727071234180737598218799951534234543378399979752798068419391\
685695639901293819346565671477580868238380412553762979132983506922946179500973\
072372424091529904207804929101962778315249964580860051623143057650828636903087\
650623239143936006261150196496039481125561859063003657456016876692219912939303\
649934354778682344087738334907714597132022551016198550077885091046612827158005\
453598886187110398597200226377804497269029390956581922772703957491877283521833\
965234557695713460434691524624004641891116966778782086446668382240671501784352\
373238026648784964313795279800042535828939669809858825678066470949394066866368\
262586823870575772795715659871488688784571302049765248202412089169503930888323\
490599966649336723180433651341659104751497601669850613850766771038237652690907\
418137856980444540467157304473112552153874924888132582078641299615430186549315\
483324262224728456537845375403309003522563763238477354542543592550315529517156\
814419992899751548087671397876713920287611278978620445452464320532087971300959\
077998059996490901450696056315029537312856613776672169545919311899621675022695\
254885190205431980383273313913364812238498968746386179758801519705215897374177\
515178886417271457708636987219068491272550942476104795618739636387669695044160\
443711597588785736901437166726709284506807205126241130231559983686986674496963\
341026521216910639932756913331939421399194056926049943917121348122841258445769\
119538929447744127511497195327108109429829422327465656942599007741240566424714\
476043257543229725866525139953103146571521055166983319403113055836697413346040\
732276457682366848413125745194735702656462473855274163364200920654288362133869\
263000408899578445934530470648567304977734981591427555431589431081364832921537\
320095286343985093254519754084126368354959325884076339776609628654646729053610\
754938871175807512231953221057185432548282454336951212492694671240112985207041\
278870849595125215446466044859452999934873724205936454142547145100218314709733\
566550109948420360572729361392113710992402646954417984933510209670249498431849\
100807846135497641988407744753491370752965599200990864318146914710140179218983\
842258654894637153469153812278058950298522443374144945961403317352489332819017\
362089054376506785537097934309720430913246306232090568916492681494152379040212\
467592300327708797959539778376158850198335903236688185013875280528527762909990\
383511389348218424714448735778715718507269113416719058132140454167547944285167\
508562348694369720572499420547037166998472329319668865080258418737293784628369\
116396967443353954193339076191448971308916427959775389107197691219066540903585\
843396201421682561264380473222295169713288050744782428013579400569861165347801\
740958755792598216905044291792575500887961296663574454157657015014794662012832\
002763987953996864811130510341906634257143039133477910171960514510326773417300\
473350876261727637054579584094615225038191328108855914857992322565158030357029\
948694667751167287226128755830073291955994960608682299840800136371303082193744\
102984706514935794768294085837145063769215606265902771574069545414198048071682\
323953018978863908610461546156004162901986384823772103911557900478950149990147\
505642664635313842039606239287972229581707268402575983318389255488573245848455\
672051513804995262247510365565343775075398971487108014908523800542298273812311\
891009565647082789733497736679341679613362798203424057176142401292361689914382\
600656643076243695475065503125124713563303612336242545180794074700756287428778\
918043850756404664697029692492317678961386639599904615136222047774182637237883\
582038612300586126006812687129636338394989180638835422270047472081947444527380\
590474160031930624241375064121019415304653566732088972342211810949500111959095\
011659481725841299033883029036542767843383377165673198140517988235663348811804\
380190747862108749889646024182989130466206454334313388265808747847693185414083\
846907193092393416556105411497066769114689573399652247156075189966590116140386\
024299086892962087455129066805108952049644614913789438084914079647893567959676\
900193774643239455728954737417343518742297186938749892875005282590763806410508\
343440551321139153691492802683069617087386978139831173995574941770196218409212\
086200402559581963745903809226209167667567320315027041696858734517597712537031\
481306983739528080579374622370200807888569632824561038555301130064947884319827\
573391049544447546654993147085501593897075354256479398825280710704693246089049\
544233251458129335315549062693514323110980809159958128694466940307392240769241\
118169392673506207828271638716787304653644293263205010248938261256488472601055\
821780090511720169053009134349232423810588661841217966450172198109392679232730\
595007818198254921826376858500505686299849027959021412012184814724881786371951\
668164206022905059852364989992302711809736691284928294640795189921639147009924\
650282186949665024092458113495124905683278972982377212979145794201591378761625\
488243059789755743738286227419164973798162967975446589964441830994494819573900\
817991663859116404727330000723620324426994450712204462960582580194486365653844\
270278424077064126226480523602393447511372932688789465431452363631837605612532\
972920400444096699455687738764897304770578984415450917343085944682174835992976\
032109663793736157173096599930006009196502279311229593159433146219733056913413\
467552179773553196794161284567014689331940232843120310294737419642804285393711\
423142039441538552804116540852527085831052031390968590250230892958728434286639\
030114504755247612648263356452731995160976995390550000062104315649414537804526\
039500531080784141890907315815476835485667012616479169122239684554640700775183\
357322802537034848032140383973736546694162487667323503483745793562451900943135\
221737570340620888370840573789605697469492243553016237126377167013785598471254\
099282306926679184768973077096472867165675822972745199941777989313088851497198\
503083648676778655693971659405157247801978509297794003926428010451337912177800\
984617926928081340343106635444992606093461930025856987540144386957289542712917\
708404919440142785591004965606390335022886056059514560248768675087413439764323\
447877144011250556103187246077786973347672777353815550684934380536899468069334\
104716136402315974341243242034684301593178102332747368012628020715027261952950\
717174690818654516595206965149573075967691524795498691231398313987841940244411\
503309410056436795336137181380745781817674535875910686428675852120624771185051\
339088218274761410431459347482785946119131434469998295202470762186075662087296\
135360849993093629832279709005000897185086161787695581730439201011882290665996\
324005537416847036797238552005884909301698377453218545651175892922885429563912\
177380161406881091927909681169361647145140516691522268369182236591244089063250\
722219544526066675698553828609740161485112326877077404225835880828594404528752\
645291083854562674855334557715603138349329916462980744602616541860699285164984\
798192895527446260336716079018511929124606869940323998112697771772676180970532\
359193310838696649412166913286939973669672830683499051070065499204851250690065\
504487276965856911392035288639223599696403047515257815189448945589325275527098\
679774285846725549341313740869610743497323830419065537721433043215944536924524\
801036593430833634879594218476429290634411658113636300276587779353098788310947\
311612016576200788564508545765989078665078238775403403798692805091270194379513\
771213576693663076655553214429405962208469877871717698214751284033378163037027\
352842789483881456533941519746065256577358203657071498254689763978041880623955\
624992088107444673379737379910877901527138435519809445676336545076159626449560\
376258986949708740935229676156065020949142040101333720617311087496950937048620\
249126196786856757295909142455341929294951575589767897131494456436796716195519\
562140225871603517094682863841783340489763659406899748637217465841894573740040\
966769507586045010121376567904151561203530561170939812615397353860437535040722\
861861478623087208945497542668097402364755944894931538172091982866316719089671\
197010935298331824522738137968975910481124101689354488105480936542378324151778\
410298472456436712028126124096329884422618433678522744923557563296079894517632\
855829781386488118672858627276817614437354986419894375337683764370341659260899\
930098271828637144120827479441374100250993669840592990189711301487522351593071\
175958919415269085833452570833170030323410707882632212589559203309664523681347\
266230119662136433541970929944591974581775757807462092622755071708607931198268\
145076669606688773627580584924006971889179772642235632659459328636646225258853\
681966039357622569387136669028439552075322574132780666941913614478227217311865\
297407122660308267528211762388953433888351958220218064117341597613031796739395\
792714357542765795713310966300273323238695820486313849792265345047598962756360\
628315846503874512854723691922386796899425981993648027757148702912794982969211\
303044363008602916115389459319185919129138479226248232499999082412983892658373\
588602312710263306662723917070061432329635679098672121271050410542240345219939\
492552261821383164892224550354599814773778064409964271666595027721571118948230\
992686372800643295243953039801927154175423090690212665499447016872583555371536\
264906340196162151629347498654262628419068821617586249197148112458119129068518\
423176656964443348249884049727303052353845627533793548255415379722587083880670\
290048504531292149400660091091051455547924389498044125000185195346879701814987\
361027130077851038191186314293553929165811896495035105781648736427876923823624\
768556539196800364398174684805457469731603343132220210212550963453193003362346\
468909055907732697150381831015204013298406927379240871693129558072729707184580\
186305511526504253087518392996754432160895981300901613873794926202942970828640\
750620801814886309886755792369484469762219427621500374445426505055535618846559\
625798292797493628623154114159714812370865956651014678432365638930493567261308\
624369534425813522121514833344781103815971440711490729155577410328460294713168\
687538876895068432269991274067994026903416785038896571361541303609542021572477\
283290112854604217168721459062100983570406041828305111516185793494640719525280\
321037660778187854272427121274693646841614773114629331914043876461178708577614\
672949377315785003233222172033697629805828484923101201035586611110801564056702\
515983636510519915662177211455514860612627111290387226342062463771610328623092\
311591931439907930515026151750370729794101911358997776446912891731856719690981\
664641988144554517952356620969405917619186043000005226684926350515586666367110\
655012924603403087197954913223627768123402156734647020882107779068271757893924\
400333346601020983665753752380316448879492545289577350363769404511485526153633\
916424642351756655525625779848292754446427439238789386915794753418875191300766\
087317039215977700865800553555980632395672950776557739486621221226750242443829\
961886822147746380782120788024438300999465915670715637846486205736110140006355\
250501756241731915991289228407070482062440226650927304051237685593384586751820\
994166564513077204559550700408853067584087279027374610360726415167811095207945\
070368536084278972708171153824639199142819329997365249090059678766179900067291\
011811318063632200285996597783481719626056756533732749758935428178616009532312\
523241529530514747068045699603447571812350441740724975901200751983382333541913\
616481607684464176934677013349347473460390436461735160034214478443053367871904\
644695459571590756389942206083883967975945038108652490167388008907582621076058\
364032796171555869574400553472183778859582997498689505161578416193796495005629\
339728133566955329933049335005340444045664170764049849110489778563710030306418\
942460701426718421476100331778766147603319556605218391944305388717602011582995\
525896484315136646218682866690111547817419287540024358412444789798000300619820\
008084376282853757066835678408384432512893888927235687629418931188524895254286\
282518551658541387422684505377157538289438812633592177945807018814221530339537\
023823762258847133425952000610153318942498507904925035899572047389921296712310\
871293762344931496148712720252559295454286132030454295498807644259053650236246\
436605297279273224364212926350852243518619271445114717011147519386343597891376\
064100978060545257556915341677329403990752913344788904724739563927716176673217\
586316522295965674857747582919853395235408337625247473596986144786956096530407\
961206712933651337658851096669480316796245691355006495606416559348185888411546\
495061352191788555195725779362704425650016522796489488048232237962674527005987\
965931850541039672779060923711767958680300520578127323380879115953978628295737\
363099389347167408286668126997618558467774797660081540113768770882941621326231\
798154149127842271178186709561941951080565398363552410386287351350878707609284\
425592943648720968915261099038978754727407689996523141553714997221613228145665\
572643649073708627625259924573490091532709381007455867364979583087822674187339\
352462030958699662563901003582427314450803786364314594529083997179350694995216\
909833889791791458841877557330842007898353311195071006276395571076278712615298\
792423496125087488256647104110408420493775361643842336246812408798810156340865\
816277334649488171225771300429370858287309310305397313587754622261862710040219\
216020512064108332941065164124122249270390557220499438217159024494883445909983\
725618515577365934961856672437431385396228651372975227146239880636793744343330\
432126442563107665088064705476306968595727597629564708571849767226932458357239\
536316359257650154654709601215251399301183550614052400956952144786861527636964\
583810120404367137178474413738789924437502024257213179224852828556007559500126\
948688599817481827330434634041214374947601458440559056883819756862448124537321\
8157000453169824579899621376

#
# test InversModInt / INVMODINT
#
gap> for m in [1..100] do
>   for b in [1..100] do
>     i := INVMODINT(b,m);
>     g := GcdInt(b,m);
>     if g = 1 then
>       Assert(0, i in [0..m-1]);
>       Assert(0, (i*b-1) mod m = 0); # formulated this way to support m=1
>       Assert(0, i = INVMODINT(b,-m));
>     else
>       Assert(0, i = fail);
>     fi;
>   od;
> od;

#
gap> INVMODINT(1,0);
Error, INVMODINT: <mod> must be a nonzero integer (not the integer 0)
gap> INVMODINT(2,10);
fail
gap> INVMODINT(2,-10);
fail
gap> INVMODINT(2,2^80);
fail
gap> INVMODINT(2,1);
0
gap> INVMODINT(2,-1);
0

#
# test PowerModInt
#
gap> for m in [1..100] do
>   for b in [-30..30] do
>     for e in [0..10] do
>       Assert(0, PowerModInt(b,e,m)=(b^e mod m));
>     od;
>   od;
> od;

#
gap> PowerModInt(1,1,0);
Error, PowerModInt: <mod> must be a nonzero integer (not the integer 0)
gap> PowerModInt(0,-1,5);
Error, PowerModInt: negative <exp> but <base> is not invertible modulo <mod>
gap> PowerModInt(2,-1,5);
3
gap> PowerModInt(2,-1,10);
Error, PowerModInt: negative <exp> but <base> is not invertible modulo <mod>

# compare C and GAP implementation
gap> POWERMODINT_GAP := function ( r, e, m )
>     local   pow, f;
> 
>     # handle special cases
>     if m = 1  then
>         return 0;
>     elif e = 0 then
>         return 1;
>     fi;
> 
>     # reduce `r' initially
>     r := r mod m;
> 
>     # if `e' is negative then invert `r' modulo `m' with Euclids algorithm
>     if e < 0  then
>         r := 1/r mod m;
>         e := -e;
>     fi;
> 
>     # now use the repeated squaring method (right-to-left)
>     pow := 1;
>     f := 2 ^ (LogInt( e, 2 ) + 1);
>     while 1 < f  do
>         pow := (pow * pow) mod m;
>         f := QuoInt( f, 2 );
>         if f <= e  then
>             pow := (pow * r) mod m;
>             e := e - f;
>         fi;
>     od;
> 
>     # return the power
>     return pow;
> end;;
gap> for m in [1..100] do
>   for b in [-30..30] do
>     for e in [0..30] do
>       Assert(0, POWERMODINT_GAP(b,e,m)=PowerModInt(b,e,m));
>       if GcdInt(m,b) = 1 then
>         Assert(0, POWERMODINT_GAP(b,-e,m)=PowerModInt(b,-e,m));
>       fi;
>     od;
>   od;
> od;

#
# test PVALUATION_INT
#
gap> checkPValuationInt:=function(n,p)
>   local k, m;
>   k:=PVALUATION_INT(n,p);
>   if n = 0 or p = 1 or p = -1 then return k = 0; fi;
>   m:=n/p^k;
>   return IsInt(m) and (m mod p) <> 0;
> end;;
gap> ps := [-2^60-1,-2^60,-2^28-1,-2^28];;
gap> Append(ps, [-6..-1]);
gap> Append(ps, [1..20]);
gap> Append(ps, [250..260]);
gap> Append(ps, [2^28-1,2^28,2^60-1,2^60]);;
gap> SetX([-1000 .. 1000], ps, checkPValuationInt);
[ true ]
gap> SetX([-1000 .. 1000], ps, {n,p}->checkPValuationInt(n+2^100,p));
[ true ]
gap> SetX([-1000 .. 1000], ps, {n,p}->checkPValuationInt(n-2^100,p));
[ true ]

#
gap> p:=2^255-19;; # big prime
gap> ForAll([1..30], k-> PVALUATION_INT((p+1)^k,2)=k);
true
gap> ForAll([1..30], k-> PVALUATION_INT((p+1)^k,p)=0);
true
gap> ForAll([1..30], k-> PVALUATION_INT(p^k+1,2)=1);
true
gap> ForAll([1..30], k-> PVALUATION_INT(p^k+1,p)=0);
true

#
gap> SetX(data, dataNonZero, checkPValuationInt);
[ true ]
gap> List([2..6], p->List(data, n->PVALUATION_INT(n,p)));
[ [ 0, 20, 4, 0, 0, 0, 4, 20, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0 ], 
  [ 0, 10, 2, 0, 0, 0, 2, 10, 0 ], [ 0, 20, 4, 0, 0, 0, 4, 20, 0 ], 
  [ 0, 0, 0, 0, 0, 0, 0, 0, 0 ] ]
gap> PVALUATION_INT(10,0);
Error, PVALUATION_INT: <p> must be a nonzero integer (not the integer 0)
gap> PVALUATION_INT(0,0);
Error, PVALUATION_INT: <p> must be a nonzero integer (not the integer 0)
gap> PVALUATION_INT(fail,1);
Error, PVALUATION_INT: <n> must be an integer (not the value 'fail')
gap> PVALUATION_INT(1,fail);
Error, PVALUATION_INT: <p> must be an integer (not the value 'fail')

#
# test ROOT_INT
#
gap> checkROOT_INT:=function(n,k)
>   local r;
>   r:=RootInt(n,k);
>   return r^k <= n and n < (r+1)^k;
> end;;
gap> SetX([0 .. 10000], [1,2,3,5,7,251,256], checkROOT_INT);
[ true ]
gap> ForAll([1..70], k -> checkROOT_INT(bigPos,k));
true
gap> SetX([1 .. 10000], [3,5,7,251,bigPos+1], {n,k} -> RootInt(n,k) = -RootInt(-n,k));
[ true ]
gap> ForAll([1,3..71], k -> RootInt(bigNeg,k) = -RootInt(bigPos,k));
true
gap> Set([1 .. 10000], n -> RootInt(n, bigPos));
[ 1 ]
gap> Set([1,2^28-1,2^28,2^60-1,2^60,bigPos], k -> RootInt(0, k));
[ 0 ]
gap> RootInt(bigPos, bigPos);
1
gap> RootInt(bigNeg, bigPos+1);
-1
gap> RootInt(bigNeg, bigPos);
Error, Root: <n> is negative but <k> is even
gap> RootInt(-2, 2);
Error, Root: <n> is negative but <k> is even
gap> RootInt(100, 2^100);
1
gap> RootInt(2^100, 2^100);
1
gap> RootInt(-2^100, 2^100);
Error, Root: <n> is negative but <k> is even
gap> RootInt(0, 0);
Error, Root: <k> must be a positive integer
gap> RootInt(fail, 1);
Error, ROOT_INT: <n> must be an integer (not the value 'fail')
gap> RootInt(1, fail);
Error, ROOT_INT: <k> must be an integer (not the value 'fail')

#
# test IS_PROBAB_PRIME_INT
#
gap> ForAll([-100..10000], n -> IS_PROBAB_PRIME_INT(n, 5) = IsProbablyPrimeInt(n));
true
gap> Filtered([-100..100], n -> false <> IS_PROBAB_PRIME_INT(2^255+n, 5));
[ -31, -19, 95 ]
gap> Filtered([-100..100], n -> false <> IsProbablyPrimeInt(2^255+n));
[ -31, -19, 95 ]
gap> IS_PROBAB_PRIME_INT(fail, 1);
Error, IS_PROBAB_PRIME_INT: <n> must be an integer (not the value 'fail')
gap> IS_PROBAB_PRIME_INT(1, fail);
Error, IsProbablyPrimeInt: <reps> must be a positive small integer (not the va\
lue 'fail')
gap> IS_PROBAB_PRIME_INT(1, 2^100);
Error, IsProbablyPrimeInt: <reps> must be a positive small integer (not a larg\
e positive integer)
gap> IS_PROBAB_PRIME_INT(1, 0);
Error, IsProbablyPrimeInt: <reps> must be a positive small integer (not the in\
teger 0)

#
# test SmallestRootInt
#
gap> SetX(Primes, [1..30], {p,k}->SmallestRootInt(p^k)=p);
[ true ]
gap> SetX(Primes, [1..30], {p,k}->SmallestRootInt(p^k*1009)=p^k*1009);
[ true ]
gap> SetX(Primes, [1..30], {p,k}->SmallestRootInt((p*1009)^k)=p*1009);
[ true ]
gap> p:=2^255-19;; # big prime
gap> ForAll([1..30], k-> SmallestRootInt(p^k) = p);
true
gap> List([-10..10], SmallestRootInt);
[ -10, -9, -2, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10 ]
gap> List(data, SmallestRootInt);
[ -100000000000000000001, -10000, -10000, -1, 0, 1, 10, 10, 
  100000000000000000001 ]
gap> List([-2^101,-2^100,2^100,2^101], SmallestRootInt);
[ -2, -16, 2, 2 ]

#
# test IsPrimePowerInt
#
gap> P:=2^255-19;; # big prime
gap> Filtered([-10..10], IsPrimePowerInt);
[ -8, -7, -5, -3, -2, 2, 3, 4, 5, 7, 8, 9 ]
gap> SetX(Primes, [1..30], {p,k}->IsPrimePowerInt(p^k));
[ true ]
gap> SetX(Primes, [1..10], {p,k}->IsPrimePowerInt(P*p^k));
[ false ]
gap> SetX(Primes, [1..10], {p,k}->IsPrimePowerInt((P*p)^k));
[ false ]
gap> ForAll([1..30], k->IsPrimePowerInt(P^k));
true
gap> ForAll([1..10], k->not IsPrimePowerInt(1009*P^k));
true
gap> ForAll([1..30], k->not IsPrimePowerInt((1009*P)^k));
true

#
gap> STOP_TEST("intarith.tst");
